package com.zyk.leetcode;

/**
 * https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/
 *
 * @author zhangsan
 * @date 2021/3/31 17:52
 */
public class J26 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            val = x;
        }
    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        // 自己先玩一遍, 然后在左边玩 右边玩, 之间又名中直接返回
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    public static boolean recur(TreeNode A, TreeNode B) {
        if(B == null) {
            return true;
        }
        if( A == null || A.val != B.val ) {
            return false;
        }
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

    // for test
    public static void main(String[] args) {
        TreeNode root       = new TreeNode(1);
        root.left           = new TreeNode(2);
        root.left.left      = new TreeNode(4);
        root.left.right     = new TreeNode(5);
        root.right          = new TreeNode(3);
        root.right.left     = new TreeNode(6);
        root.right.right    = new TreeNode(7);


        TreeNode B          = new TreeNode(3);
        B.left              = new TreeNode(6);
        B.right             = new TreeNode(7);
        System.out.println(isSubStructure(root, B));

    }

}
